{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Winner of an Array Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getWinner"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出数组游戏的赢家"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <strong>不同</strong> 整数组成的整数数组 <code>arr</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>每回合游戏都在数组的前两个元素（即 <code>arr[0]</code> 和 <code>arr[1]</code> ）之间进行。比较 <code>arr[0]</code> 与 <code>arr[1]</code> 的大小，较大的整数将会取得这一回合的胜利并保留在位置 <code>0</code> ，较小的整数移至数组的末尾。当一个整数赢得 <code>k</code> 个连续回合时，游戏结束，该整数就是比赛的 <strong>赢家</strong> 。</p>\n",
    "\n",
    "<p>返回赢得比赛的整数。</p>\n",
    "\n",
    "<p>题目数据 <strong>保证</strong> 游戏存在赢家。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,1,3,5,4,6,7], k = 2\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>一起看一下本场游戏每回合的情况：\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/30/q-example.png\" style=\"height: 90px; width: 400px;\">\n",
    "因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [3,2,1], k = 10\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>3 将会在前 10 个回合中连续获胜。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,9,8,2,3,7,6,4,5], k = 7\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000\n",
    "<strong>输出：</strong>99\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= arr.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10^6</code></li>\n",
    "\t<li><code>arr</code> 所含的整数 <strong>各不相同</strong> 。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-winner-of-an-array-game](https://leetcode.cn/problems/find-the-winner-of-an-array-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-winner-of-an-array-game](https://leetcode.cn/problems/find-the-winner-of-an-array-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3,5,4,6,7]\\n2', '[3,2,1]\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        i = 0\n",
    "        t = 0\n",
    "        while t < k and i < len(arr) - 1:\n",
    "            if arr[i] > arr[i+1]:\n",
    "                arr[i+1] = arr[i]\n",
    "                t += 1\n",
    "            else: \n",
    "                t = 1\n",
    "            i += 1\n",
    "        return arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        cnt = 1\n",
    "        pre = max(arr[0], arr[1])\n",
    "        if k == 1:\n",
    "            return pre\n",
    "        \n",
    "        maxNum = pre\n",
    "\n",
    "        for i in range(2, len(arr)):\n",
    "            cur = arr[i]\n",
    "            if pre > cur:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return pre\n",
    "            else:\n",
    "                pre = cur\n",
    "                cnt = 1\n",
    "            maxNum = max(maxNum, pre)\n",
    "        \n",
    "        return maxNum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        pre, c = arr[0], 0\n",
    "        for num in arr[1:]:\n",
    "            if num > pre:\n",
    "                pre = num\n",
    "                c =1\n",
    "            else:\n",
    "                c +=1\n",
    "            if c == k:\n",
    "                return pre\n",
    "        return max(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        cur=arr[0] \n",
    "        cnt= 0 \n",
    "        mmax= max(arr) \n",
    "        for i in arr[1::]: \n",
    "            if cur>i:\n",
    "                cnt+=1 \n",
    "            else: \n",
    "                cur=i   \n",
    "                cnt=1 \n",
    "            if cnt>=k: return cur       \n",
    "        return mmax  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        pre = max(arr[0], arr[1])\n",
    "        cnt = 1\n",
    "        if k == 1:\n",
    "            return pre\n",
    "        for x in arr[2:]:\n",
    "            if x < pre:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return pre\n",
    "            else:\n",
    "                pre = x\n",
    "                cnt = 1\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "#   Collections.swap(list,a,b)；（注意：索引为a的元素与索引为b的元素交换位置，其他元素的索引值不变）\n",
    "\n",
    "#   list是你需要换位置的List。\n",
    "\n",
    "#   a是你当前需要换位置的元素的索引。\n",
    "\n",
    "#   b是你需要将这个元素换到哪个索引。\n",
    "\n",
    "# 2.list.add(0, list.remove(i))；（注意：先移除，然后把移除的元素放在指定位置，指定位置之后元素的索引值往后加1）\n",
    "\n",
    "\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        temp=max(arr[0],arr[1])\n",
    "        p=2\n",
    "        count=1\n",
    "        while count<k and p<=n-1:\n",
    "                maxv=max(temp,arr[p])                \n",
    "                if temp==maxv:count=count+1\n",
    "                else: count=1\n",
    "                temp=maxv\n",
    "                p=p+1\n",
    "        return temp\n",
    "                \n",
    "              \n",
    "                     \n",
    "                     \n",
    "        \n",
    "           \n",
    "                \n",
    "            \n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        arr_len = len(arr)\n",
    "        if k >= arr_len:\n",
    "            return max(arr)\n",
    "        n = 0\n",
    "        num = 1\n",
    "        maxval = arr[0]\n",
    "        while n < k and num <arr_len:\n",
    "            a1 = arr[num]\n",
    "            num += 1\n",
    "            if maxval > a1:\n",
    "                n += 1    \n",
    "            else:\n",
    "                maxval = a1\n",
    "                n = 1\n",
    "        return maxval\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    a = Solution()\n",
    "    arr = [1,9,8,2,3,7,6,4,5]\n",
    "    k = 7\n",
    "    a.getWinner(arr, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        pre = max(arr[0], arr[1])\n",
    "\n",
    "        if k == 1:\n",
    "            return pre\n",
    "\n",
    "        cnt = 1\n",
    "        ans = pre\n",
    "        for i in range(2, n):\n",
    "            cur = arr[i]\n",
    "            if cur < pre:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return pre\n",
    "            else:\n",
    "                pre = cur\n",
    "                cnt = 1\n",
    "            ans = max(ans, cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        idx, cnt = 0, 0\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[idx] > arr[i]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                idx = i\n",
    "                cnt = 1\n",
    "            if cnt == k:\n",
    "                break\n",
    "        return arr[idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return max(arr[:2])\n",
    "        pre = max(arr[:2])\n",
    "        cnt = 1\n",
    "        for i in range(2, len(arr)):\n",
    "            cur = arr[i]\n",
    "            if pre > cur:\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    return pre\n",
    "            else:\n",
    "                pre = cur\n",
    "                cnt = 1\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        last = 0\n",
    "        for i in range(1,n):\n",
    "            if arr[i]>arr[last]:\n",
    "                if i -last + int(last!=0)>k:\n",
    "                    return arr[last]\n",
    "                last = i\n",
    "        return arr[last]\n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        prev = max(arr[0], arr[1])\n",
    "        if k == 1:\n",
    "            return prev\n",
    "\n",
    "        consecutive = 1\n",
    "        maxNum = prev\n",
    "        length = len(arr)\n",
    "\n",
    "        for i in range(2, length):\n",
    "            curr = arr[i]\n",
    "            if prev > curr:\n",
    "                consecutive += 1\n",
    "                if consecutive == k:\n",
    "                    return prev\n",
    "            else:\n",
    "                prev = curr\n",
    "                consecutive = 1\n",
    "            maxNum = max(maxNum, curr)\n",
    "        \n",
    "        return maxNum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        mv = max(arr)\n",
    "        md, cnt, n = 1, 0, len(arr)\n",
    "        while cnt != k:\n",
    "            if arr[0] == mv: return mv\n",
    "            if arr[0] > arr[md]: cnt += 1\n",
    "            else:\n",
    "                #print(arr[0], cnt)\n",
    "                t = arr[md]\n",
    "                arr[md] = arr[0]\n",
    "                arr[0] = t\n",
    "                cnt = 1\n",
    "            md += 1\n",
    "            if md == n: md = 1\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        prev = max(arr[0], arr[1])\n",
    "        if k == 1:\n",
    "            return prev\n",
    "\n",
    "        consecutive = 1\n",
    "        maxNum = prev\n",
    "        length = len(arr)\n",
    "\n",
    "        for i in range(2, length):\n",
    "            curr = arr[i]\n",
    "            if prev > curr:\n",
    "                consecutive += 1\n",
    "                if consecutive == k:\n",
    "                    return prev\n",
    "            else:\n",
    "                prev = curr\n",
    "                consecutive = 1\n",
    "            maxNum = max(maxNum, curr)\n",
    "        \n",
    "        return maxNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        last = 0\n",
    "        for i in range(1,n):\n",
    "            if arr[i]>arr[last]:\n",
    "                if i -last + int(last!=0)>k:\n",
    "                    return arr[last]\n",
    "                last = i\n",
    "        return arr[last]\n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        idx = 2\n",
    "        cnt = 1\n",
    "        pre = arr[0] if arr[0] > arr[1] else arr[1]\n",
    "        if cnt == k:\n",
    "            return pre\n",
    "        while idx < n:\n",
    "            if arr[idx] > pre:\n",
    "                cnt = 1\n",
    "                pre = arr[idx]\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if cnt == k:\n",
    "                return pre\n",
    "            idx += 1\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        if len(arr)<=k:\n",
    "            return max(arr)\n",
    "        cnt=0\n",
    "        n=len(arr)\n",
    "        win_num=arr[0]\n",
    "        for i in range(1,n):\n",
    "            if arr[i]>win_num:\n",
    "                cnt=1\n",
    "                win_num=arr[i]\n",
    "            else:\n",
    "                cnt=cnt+1\n",
    "            if cnt==k:\n",
    "                return win_num\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        count = [0] * n\n",
    "        # 不会第二次见到放到后面的数了\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while j < n:\n",
    "            if arr[i] < arr[j]:\n",
    "                count[j] += 1\n",
    "                if count[j] == k:\n",
    "                    return arr[j]\n",
    "                i = j\n",
    "                j += 1\n",
    "            else:\n",
    "                count[i] += 1\n",
    "                if count[i] == k:\n",
    "                    return arr[i]\n",
    "                j += 1\n",
    "        return arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        if k > len(arr):\n",
    "            return max(arr)\n",
    "        num, win = arr[0], 0\n",
    "        for a in arr[1:]:\n",
    "            if a > num:\n",
    "                num, win = a, 0\n",
    "            win += 1\n",
    "            if win == k:\n",
    "                return num \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        if k >= n-1:\n",
    "            return max(arr)\n",
    "        res = arr[0]\n",
    "        cnt = 0\n",
    "        for i in range(1, n):\n",
    "            if res >= arr[i]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                res = arr[i]\n",
    "                cnt = 1\n",
    "            if cnt == k:\n",
    "                return res\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        winner, wins = arr[0], 0\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] > winner:\n",
    "                winner, wins = arr[i], 1\n",
    "            else:\n",
    "                wins += 1\n",
    "            if wins == k:\n",
    "                return winner\n",
    "        return winner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: list[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        winnum = max(arr[0],arr[1])\n",
    "        wintime = 1\n",
    "        if k == 1:\n",
    "            return winnum\n",
    "        \n",
    "        for i in range(2,n):\n",
    "            cur = arr[i]\n",
    "            if winnum > cur:\n",
    "                wintime += 1\n",
    "                if wintime == k:\n",
    "                    return winnum\n",
    "            else:\n",
    "                winnum = cur\n",
    "                wintime = 1\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        cur_max = arr[0]\n",
    "        cnt = 0\n",
    "        for x in arr[1:]:\n",
    "            if x > cur_max:\n",
    "                cnt = 1\n",
    "                cur_max = x\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if cnt >= k:\n",
    "                return cur_max\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        cur = arr[0]\n",
    "        n = 0\n",
    "        for i in arr[1:]:\n",
    "            if i > cur:\n",
    "                cur = i\n",
    "                n = 1\n",
    "            else:\n",
    "                n += 1\n",
    "            if n == k:\n",
    "                return cur\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        cwinner = arr[0]   # 初始赢家\n",
    "        countn = 0         # 连胜次数\n",
    "        for x in arr[1:]:\n",
    "            if cwinner>x:  \n",
    "                countn += 1  # 连胜次数+1\n",
    "            else:\n",
    "                cwinner = x  # 碰到比它大的，进行替换\n",
    "                countn = 1   # 连胜终结\n",
    "            if countn >=k:   # 达到k值，返回当前赢家\n",
    "                return cwinner\n",
    "        return cwinner       # 一趟遍历结束之后，最大值到达首部，此时返回的一定是最大值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        a,n=arr[0],0\n",
    "        for i in arr[1:] :\n",
    "            if i>a :\n",
    "                a,n=i,1\n",
    "            else :\n",
    "                n+=1\n",
    "            if n==k :\n",
    "                return a\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        prev = max(arr[0], arr[1])\n",
    "        if k == 1: return prev\n",
    "        \n",
    "        consecutive = 1\n",
    "        maxNum = prev\n",
    "        length = len(arr)\n",
    "\n",
    "        for i in range(2, length):\n",
    "            curr = arr[i]\n",
    "            if prev > curr:\n",
    "                consecutive += 1\n",
    "                if consecutive == k:\n",
    "                    return prev\n",
    "            else:\n",
    "                prev = curr\n",
    "                consecutive = 1\n",
    "            maxNum = max(maxNum, curr)\n",
    "        \n",
    "        return maxNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        a,n=arr[0],0\n",
    "        for i in arr[1:] :\n",
    "            if i>a :\n",
    "                a,n=i,1\n",
    "            else :\n",
    "                n+=1\n",
    "            if n==k :\n",
    "                return a\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        if k >= len(arr)-1:\n",
    "            return max(arr)\n",
    "        res = arr[0]\n",
    "        cnt = 0\n",
    "        for v in arr[1:]:\n",
    "            if res >= v:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                res = v\n",
    "                cnt = 1\n",
    "            if cnt == k:\n",
    "                return res\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        mx = arr[0]\n",
    "        cnt = 0\n",
    "        for cur in arr[1:]:\n",
    "            if mx > cur:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                mx = cur \n",
    "                cnt = 1\n",
    "            if cnt == k:\n",
    "                return mx \n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        if k>= n:\n",
    "            return max(arr)\n",
    "        maxn = max(arr)\n",
    "        cnt = 1\n",
    "        prev = max(arr[0], arr[1])\n",
    "        if prev == maxn or k == 1:\n",
    "            return prev\n",
    "        for i in range(2,n):\n",
    "            if arr[i]<prev:\n",
    "                cnt += 1\n",
    "                if cnt == k :\n",
    "                    return prev\n",
    "            else:\n",
    "                cnt = 1\n",
    "                prev = arr[i]\n",
    "            if prev == maxn:\n",
    "                return prev\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "        # dic = defaultdict(int)\n",
    "        # while len(arr)>=2:\n",
    "        #     first = arr[0]\n",
    "        #     second = arr[1]\n",
    "        #     if first>second:\n",
    "        #         arr.pop(1)\n",
    "        #         dic[first] += 1\n",
    "        #         if first == maxn or dic[first] ==k:\n",
    "        #             return first\n",
    "        #     else:\n",
    "        #         arr.pop(0)\n",
    "        #         dic[second] += 1\n",
    "        #         if second == maxn or dic[second] ==k:\n",
    "        #             return second\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = {arr[0], arr[1]}\n",
    "        winner = arr[0] if arr[0] > arr[1] else arr[1]\n",
    "        cnt = 1\n",
    "        if k == 1:\n",
    "            return winner\n",
    "        for num in arr[2:]:\n",
    "            if num > winner:\n",
    "                winner = num\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if cnt == k:\n",
    "                return winner\n",
    "        return winner\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        last = 0\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] > arr[last]:\n",
    "                if i - last + int(last != 0) > k:\n",
    "                    return arr[last]\n",
    "                last = i\n",
    "        return arr[last]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        pre = max(arr[0],arr[1])\n",
    "        if k == 1:\n",
    "            return pre\n",
    "\n",
    "        count = 1\n",
    "        maxnum = pre\n",
    "\n",
    "        for i in range(2,len(arr)):\n",
    "            \n",
    "                if pre > arr[i]:\n",
    "                    count += 1\n",
    "                    if count == k:\n",
    "                        return pre\n",
    "\n",
    "                else:\n",
    "                    count = 1\n",
    "                    pre = arr[i]\n",
    "\n",
    "                maxnum = pre\n",
    "\n",
    "        return maxnum\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        win = 0\n",
    "        winCnt = 0\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[win] > arr[i]:\n",
    "                winCnt += 1\n",
    "            else:\n",
    "                win = i\n",
    "                winCnt = 1\n",
    "            if winCnt == k:\n",
    "                return arr[win]\n",
    "        return arr[win]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: list[int], k: int) -> int:\n",
    "        i, n = 0, len(arr)\n",
    "        h1 = [-x for x in arr[:k+1]]\n",
    "        heapify(h1)\n",
    "        h2 = []\n",
    "\n",
    "        while 1:\n",
    "            if arr[i] + h1[0] == 0:\n",
    "                return arr[i]\n",
    "            else:\n",
    "                heappush(h2, -arr[i])\n",
    "                if i + k < n and i != 0: heappush(h1, -arr[i + k])\n",
    "                i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#python3 tadakuso的题解\n",
    "class Solution:\n",
    "\tdef getWinner(self,arr,k):\n",
    "\t\ta,n=arr[0],0\n",
    "\t\tfor i in arr[1:]:\n",
    "\t\t\tif i>a:\n",
    "\t\t\t\ta,n=i,1\n",
    "\t\t\telse:\n",
    "\t\t\t\tn+=1\n",
    "\t\t\tif n==k:\n",
    "\t\t\t\treturn a\n",
    "\t\treturn a\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        arrSize = len(arr)\n",
    "\n",
    "        winRounds = 0\n",
    "        winIdx = 0\n",
    "        for nextIdx in range(1, arrSize):  # 2 <= arr.length <= 10^5\n",
    "            if arr[winIdx] > arr[nextIdx]:\n",
    "                winRounds += 1\n",
    "            elif arr[winIdx] < arr[nextIdx]:\n",
    "                winIdx = nextIdx\n",
    "                winRounds = 1\n",
    "            elif arr[winIdx] == arr[nextIdx]:  # arr contains distinct integers.\n",
    "                pass\n",
    "\n",
    "            if winRounds == k:\n",
    "                break\n",
    "\n",
    "        retVal = arr[winIdx]\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        if k >= len(arr)-1: return max(arr)\n",
    "        cur, tmp = arr[0], k\n",
    "        for i in range(1, len(arr)):\n",
    "            if cur > arr[i]:\n",
    "                tmp -=1\n",
    "            else:\n",
    "                cur = arr[i]\n",
    "                tmp = k-1\n",
    "            if tmp == 0:\n",
    "                return cur\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        if k >= len(arr) - 1:   return max(arr)\n",
    "        if k == 1:  return max(arr[0:2])\n",
    "        maxIndex = cnt = 0\n",
    "        n = len(arr)\n",
    "        for i in range(1, n + k - 1):\n",
    "            if arr[i % n] < arr[maxIndex]:\n",
    "                cnt += 1\n",
    "                if cnt == k:    return arr[maxIndex]\n",
    "            else:\n",
    "                maxIndex = i % n\n",
    "                cnt = 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        N = len(arr)\n",
    "        max_num = max(arr)\n",
    "        if k > N:\n",
    "            return max_num\n",
    "\n",
    "        nums = deque(arr[1:])\n",
    "        curr_num = arr[0]\n",
    "        win_streak = 0\n",
    "\n",
    "        while win_streak < k and curr_num != max_num:\n",
    "            opponent = nums.popleft()\n",
    "            if curr_num > opponent:\n",
    "                win_streak += 1\n",
    "                nums.append(opponent)\n",
    "            else:\n",
    "                win_streak = 1\n",
    "                nums.append(opponent)\n",
    "                curr_num = opponent\n",
    "                \n",
    "        return curr_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        if not arr:\n",
    "            return -1\n",
    "        flag = arr[0]\n",
    "        k = min(k, len(arr)-1)\n",
    "        count = 0\n",
    "        queue = deque(arr[1:])\n",
    "        while queue:\n",
    "            pop = queue.popleft()\n",
    "            if flag > pop:\n",
    "                count += 1\n",
    "                queue.append(pop)\n",
    "            else:\n",
    "                count = 1\n",
    "                queue.append(flag)\n",
    "                flag = pop\n",
    "            if count == k:\n",
    "                return flag\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        win = 0\n",
    "        lian = 0\n",
    "        maxnum = 0\n",
    "        for i in range (len(arr) - 1):\n",
    "            if arr[i] > maxnum:\n",
    "                maxnum = arr[i]\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                if win == arr[i]:\n",
    "                    lian += 1\n",
    "                else:\n",
    "                    lian = 1\n",
    "                win = arr[i]\n",
    "                arr[i], arr[i + 1] = arr[i + 1], arr[i]\n",
    "            else:\n",
    "                if win == arr[i + 1]:\n",
    "                    lian += 1\n",
    "                else:\n",
    "                    lian = 1\n",
    "                win = arr[i + 1]\n",
    "            if lian == k:\n",
    "                return win\n",
    "        if arr[-1] > maxnum:\n",
    "            maxnum = arr[-1]\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        win = 0\n",
    "        lian = 0\n",
    "        maxnum = 0\n",
    "        for i in range (len(arr) - 1):\n",
    "            if arr[i] > maxnum:\n",
    "                maxnum = arr[i]\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                if win == arr[i]:\n",
    "                    lian += 1\n",
    "                else:\n",
    "                    lian = 1\n",
    "                win = arr[i]\n",
    "                arr[i], arr[i + 1] = arr[i + 1], arr[i]\n",
    "            else:\n",
    "                if win == arr[i + 1]:\n",
    "                    lian += 1\n",
    "                else:\n",
    "                    lian = 1\n",
    "                win = arr[i + 1]\n",
    "            if lian == k:\n",
    "                return win\n",
    "        if arr[-1] > maxnum:\n",
    "            maxnum = arr[-1]\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        N = len(arr)\n",
    "        max_num = max(arr)\n",
    "        if k > N:\n",
    "            return max_num\n",
    "\n",
    "        nums = deque(arr[1:])\n",
    "        curr_num = arr[0]\n",
    "        win_streak = 0\n",
    "\n",
    "        while win_streak < k and curr_num != max_num:\n",
    "            opponent = nums.popleft()\n",
    "            if curr_num > opponent:\n",
    "                win_streak += 1\n",
    "                nums.append(opponent)\n",
    "            else:\n",
    "                win_streak = 1\n",
    "                nums.append(opponent)\n",
    "                curr_num = opponent\n",
    "                \n",
    "        return curr_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        q = deque(arr)\n",
    "        r = max(arr)\n",
    "        c = defaultdict(int)\n",
    "        w = q.popleft()\n",
    "        while w != r:\n",
    "            t = q.popleft()\n",
    "            if t > w:\n",
    "                t, w = w, t\n",
    "            q.append(t)\n",
    "            c[w] += 1\n",
    "            if c[w] == k:\n",
    "                break\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        win = 0\n",
    "        lian = 0\n",
    "        for i in range (len(arr) - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                if win == arr[i]:\n",
    "                    lian += 1\n",
    "                else:\n",
    "                    lian = 1\n",
    "                win = arr[i]\n",
    "                arr[i], arr[i + 1] = arr[i + 1], arr[i]\n",
    "            else:\n",
    "                if win == arr[i + 1]:\n",
    "                    lian += 1\n",
    "                else:\n",
    "                    lian = 1\n",
    "                win = arr[i + 1]\n",
    "            if lian == k:\n",
    "                return win\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        maxv = arr[0]\n",
    "        win = 0\n",
    "        for i in range(1, len(arr)) :\n",
    "            if maxv > arr[i] :\n",
    "                win += 1\n",
    "            else :\n",
    "                maxv = arr[i]\n",
    "                win = 1\n",
    "            if win == k :\n",
    "                return maxv\n",
    "        \n",
    "        return maxv\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        q = deque(arr)\n",
    "        n = len(arr) \n",
    "        cnt = 0 \n",
    "        x = -1 \n",
    "        while cnt < min(k, n):\n",
    "            a, b = q.popleft(), q.popleft() \n",
    "            if a < b:\n",
    "                cnt = 1\n",
    "                q.appendleft(b)\n",
    "                q.append(a) \n",
    "                x = b \n",
    "            else:\n",
    "                cnt += 1\n",
    "                q.append(b)\n",
    "                q.appendleft(a) \n",
    "                x = a \n",
    "        return x \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWinner(self, arr: List[int], k: int) -> int:\n",
    "        aLen = len(arr)\n",
    "        res = -1\n",
    "        if k >= aLen:\n",
    "            for a in arr:\n",
    "                res = max(res, a)\n",
    "            return res\n",
    "\n",
    "        fst , snd = arr[0] , arr[1]\n",
    "\n",
    "        queue = deque()\n",
    "        for i in range(2, len(arr)):\n",
    "            queue.append(arr[i])\n",
    "\n",
    "        count = 0\n",
    "        while count < k:\n",
    "            if fst > snd:\n",
    "                queue.append(snd)\n",
    "                count += 1\n",
    "                snd = queue.popleft()\n",
    "            else:\n",
    "                count = 1\n",
    "                queue.append(fst)\n",
    "                fst = snd\n",
    "                snd = queue.popleft()\n",
    "        \n",
    "        return fst"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
